A Physical Uncloneable Function (PUF) is a function which is embodied as a physical system, in such a way that an output of the function for an input is obtained by offering the input to the physical system in the form of a stimulus, and mapping the behavior that occurs as a result of an interaction between the stimulus and the physical system to an output. Wherein the interaction is unpredictable and depends on essentially random elements in the physical system, to such an extent, that it is unfeasible to obtain the output, without having had physical access to the physical system, and that it is unfeasible to reproduce the physical system. Preferably, a PUF is also easy to evaluate. For practical uses, PUFs are preferably low in manufacture costs.
Conventionally, an input or stimulus that a PUF accepts is called a ‘challenge’. The output of a PUF, that is, the behavior the PUF exhibits after interaction with the stimulus, is called a ‘response’. A pair comprising a challenge and the corresponding response of a PUF is called a challenge-response pair. Some types of PUFs allow a wide range of different inputs, some types allow a more limited range of inputs, or may even allow only a single input. It would be most preferable, if a PUF when evaluated multiple times for the same challenge would produce multiple responses which are all equal. This property is not necessary though, and, in practice, most PUFs do not posses it. As long as the multiple responses lie sufficiently close to each other, the PUF can be usefully applied.
Since the interaction between a stimulus and the physical system cannot be predicted without access to the system, the PUF is hard to characterize and to model. The output of a particular PUF for an input can therefore only be obtained using the particular physical system underlying the particular PUF. Possession of a challenge-response pair is proof that at some point the challenge was offered to the unique physical system that underlies the PUF. Because of this property, i.e., the property that challenge-response pairs are coupled to a unique physical device, a PUF is called uncloneable. By equipping a device with a PUF, the device also becomes uncloneable.
Physical systems that are produced by a production process that is, at least in part, uncontrollable, i.e., a production process which will inevitably introduce some randomness, turn out to be good candidates for PUFs.
One advantage of PUFs is that they inherently possess tamper resistant qualities: disassembling the PUF to observe its working, will also disturb the random elements and therefore also disturb the way inputs are mapped to outputs.
One way of constructing a PUF uses a static random access memory (SRAM); these PUFs are called SRAM PUFs. SRAMs have the property that after they are powered-up, they are filled with a random pattern of on-bits and off-bits. Although the pattern will not repeat itself exactly if the SRAM is powered-up a next time, the differences between two such patterns is typically much smaller than half the number of bits in the state.
A second kind of S-RAM PUFs is constructed with Dual Port RAM. By writing at the same time different information on both ports, the memory cell is brought into an undefined state which shows a PUF-like behavior.
One application of PUFs is to derive a cryptographic key on an electronic circuit. The electronic circuit typically includes an integrated Circuit (IC) and/or programmable logic. The programmable logic comprises, e.g., a field-programmable gate array (FPGA), a programmable logic device (PLD), or a digital signal processor (DSP), a microprocessor, etc. Instead of storing the cryptographic key in a non-volatile memory of some kind, the key is generated from the PUF only when the key is needed by the device. The key can be deleted when it is no longer needed. The next time the key is needed, it can be derived again from the PUF. Since the PUF may not give the exact same result when the same challenge is evaluated twice, a so-called Helper Data algorithm, also known as a Fuzzy Extractor, may be used to ensure that the key will be the same, each time it is derived. One way of using helper data to construct reproducible values from noisy measurements is described, e.g., in international patent application WO 2006/129242, “Template Renewal in Helper Data Systems”, etc.
One way to use a PUF to create a cryptographic key is as follow. First, during an enrollment phase, a challenge-response pair is created. Then, using the fuzzy extractor, helper data is created. On the device the challenge and the helper data are stored in a non-volatile memory. To derive the cryptographic key, a new response is obtained by evaluating the PUF for the challenge again. By combining the new response with the stored helper data, according to a helper data algorithm, a key is derived. The helper data ensures that the key is the same, each time it is derived.
Without a PUF, the cryptographic key may be recovered by an attacker, by mounting a physical attack on the non-volatile memory. For example, the attacker may open the memory and probe its content. Using a PUF makes this type of attack much harder, since opening the PUF will typically disturb the precise way in which the PUF interacts with inputs. Accordingly, information the attacker learns from his probe is not related to the interaction which was used to create the cryptographic key. This makes it harder for an attacker to find the key using a physical attack.
PUFs based on the intrinsic behavior of memory cells have the disadvantage that memory modules (especially SRAM) are typically relatively large structures that can easily be identified in an integrated circuit. An attacker, who manages to open the IC and tap the data lines to the memory without disturbing the memory itself, could obtain useful information once the IC is running and the PUF is challenged. Together with the helper data, the probed data may enable him to find the secret key back.
It is a problem of the prior art that a memory based PUF is susceptible to an attack on its data line.